Self-routing networks are well known and are commonly called banyan networks. One such switching network is disclosed in J. S. Turner, U.S. Pat. No. 4,491,945. As disclosed in Turner, the self-routing network comprises a plurality of stages with each stage having a plurality of switch nodes. Within a given stage, a switch node is responsive to the receipt of a packet from an upstream node to examine the routing information contained within the packet and to transfer that packet to the downstream switch node of the subsequent stage as designated by the routing information. In Turner, a complete path is to set up through the switching network before the packet enters the switching network, but rather, a packet is transferred from stage to stage as the designated switch node in the next stage has the capacity to accept the packet. An inter-node protocol is used to facilitate the communication of packets in this manner. In addition, each switch node has the capacity for buffering one complete packet per input terminal and indicates to the upstream node when it is capable of accepting another packet from the upstream node. Turner utilizes a single conductor both to transfer data from the upstream node to the downstream node and for the downstream node to signal the upstream node when the downstream node has the capacity for accepting another packet.
Also, Turner synchronizes the transfer of data between switch nodes by supplying to all the switch nodes of the switching network clock signals that are received by all nodes with identical phase from a common timing generator. Providing the synchronization for the switch nodes in this manner allows Turner to have only one conductor per interconnection link between two switch nodes. In Turner an inter-node protocol functions in the following way. The downstream and upstream node transmit information on the single conductor interconnecting them utilizing tri-state devices. The latter devices exhibit a high-impedance state when not transmitting information. When no information is being transmitted between the two interconnected nodes, both nodes are interrogating the conductor for information. When the downstream node is capable of receiving another packet from the upstream node, the downstream node transmits a capacity available signal to the upstream node on the conductor indicating that the downstream node has the present capacity for receiving another packet. The upstream node is responsive to the received signal to commence the transfer of another packet to the downstream node if a packet is awaiting transmission. The downstream node utilizes the common clock signal to clock the incoming packet data from the upstream node into internal storage registers where the decoding of the routing information can be accomplished for communicating this packet to the next sequential stage.
As disclosed in U.S. Pat. No. 4,314,367, R. Bakka, et al., it is known to transmit clock signals via a second conductor from the transmitting node to the receiving node using yet a third conductor to transfer a capacity-to-receive signal from the receiving node to the transmitting node. That method increases the number of conductors between switch nodes; thus reducing the number of nodes which can be placed on a printed circuit board. This limitation is due to the limited number of connections that can be made to a printed circuit board.
In addition, it is known to encode the data and clock signals together and transmit the resulting self-clocking signal via one conductor. One such self-clocking method is Manchester encoding. The problem with self-clocking methods are that those methods require the utilization of delay lines in both the transmitter and receiver. Delay lines tend to be undreliable and are difficult to fabricate on very large scale integrated circuits (VLSI).
Whereas, the inter-node protocol and synchronization disclosed in Turner works very well in many configurations of self-routing networks and is readily adaptable to VLSI implementation, it does not allow for the detection of the interlink malfunctions either during the transferring of data from the upstream to the downstream node or during the transfer of the capacity available signal from the downstream node to the upstream node. Also, problems can exist in Turner in providing clock signals that have identical phase throughout a large self-routing network. Physical factors can cause the phase of the clock signals to be different at various places in the switching network if a great deal of care is not taken in the distribution of these clock signals.